//
// B+ 树
// https://blog.csdn.net/xiaohusaier/article/details/77101640
// Created by 麻再挺 on 2021/12/20.
//

#ifndef DATA_STRUCTURE_C_BP_TREE_H
#define DATA_STRUCTURE_C_BP_TREE_H

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "./../constant.h"

// 最大叶子数
#define BP_M (4)
// 分裂结点数
#define BP_LIMIT_M_2 (BP_M % 2 ? (BP_M + 1) / 2 :  BP_M / 2)

// 数据类型
typedef int BPKeyType;

// B+树结点
typedef struct BPNode {
    // 结点数量
    int keyNum;
    // 键数组
    BPKeyType key[BP_M + 1];
    // 孩子数组
    struct BPNode *children[BP_M + 1];
    // 下一个结点
    struct BPNode *next;
} *BPTree, *BPPosition;

/**
 * 初始化
 */
BPTree BP_Initialize();

/**
 * 插入
 * @param t B+树
 * @param Key 键
 */
BPTree BP_Insert(BPTree t,BPKeyType Key);

/**
 * 删除
 * @param t B+树
 * @param Key 键
 * @return
 */
BPTree BP_Remove(BPTree t,BPKeyType Key);

/**
 * 销毁
 * @param t B+树
 */
BPTree BP_Destroy(BPTree t);

/**
 * 遍历节点
 * @param t B+树
 */
void BP_Travel(BPTree t);

/**
 * 遍历树叶节点的数据
 * @param t B+树
 */
void BP_Travel_Data(BPTree t);

#endif //DATA_STRUCTURE_C_BP_TREE_H































